perm filename A01[106,RWF] blob
sn#730318 filedate 1984-03-27 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00012 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 _Algorithms_
C00008 00003
C00012 00004 How would you add
C00014 00005 We all learned simplified rules of arithmetic in school, which work well enough
C00019 00006 Familiar algorithms include those for
C00023 00007 There is a traditional algorithm used by Russian peasants to multiply numbers
C00027 00008 The successive rows represent different formulas, but each formula stands for
C00032 00009 A more efficient formulation of Euclid's algorithm uses remainders (of division)
C00037 00010 Pascal
C00048 00011 Programs
C00051 00012 Standard Algorithms in Pascal
C00055 ENDMK
C⊗;
_Algorithms_
Originally, the word algorithm (in its older form, "algorism") meant a
method for doing arithmetic using Arabic numerals; the word came from the
name of Abu Ja'far Mohammed ibu Musa, a ninth century Arabic mathematician
and textbook author [Knuth v1,p1]. It has come to mean any completely
specified rule for processing information. Carrying out an algorithm requires
no imagination, nor any understanding of the significance of the computation.
Before the advent of the computer, huge teams of clerks were used to calculate
tables of logarithms and trigonometric functions, tables giving correct angles
for aiming artillery taking account of distance and wind, etc. Probably few of
them understood the reasons for the algorithms. Now we tend to relegate
such algorithms to electronic computers, as we shall see.
Most of us have forgotten how complicated the complete algorithms for
arithmetic are. Here is one such algorithm, to subtract B from A, giving a
result C, where A and B must both be whole numbers (integers), and A must
be greater than B.
(1). Look up the rightmost digits of A and B in Table 1.
Table 1
A\B 0 1 2 3 4 5 6 7 8 9
------------------------------------------
0 | 0 9B 8B 7B 6B 5B 4B 3B 2B 1B
|
1 | 1 0 9B 8B 7B 6B 5B 4B 3B 2B
|
2 | 2 1 0 9B 8B 7B 6B 5B 4B 3B
|
3 | 3 2 1 0 9B 8B 7B 6B 5B 6B
|
4 | 4 3 2 1 0 9B 8B 7B 6B 5B
|
5 | 5 4 3 2 1 0 9B 8B 7B 6B
|
6 | 6 5 4 3 2 1 0 9B 8B 7B
|
7 | 7 6 5 4 3 2 1 0 9B 8B
|
8 | 8 7 6 5 4 3 2 1 0 9B
|
9 | 9 8 7 6 5 4 3 2 1 0
------------------------------------------
Write down the digit from the table as the units digit of C. Remember
whether there was a B ("borrow") at the table entry. Scratch out the
rightmost digits of A and B. If there was no borrow, go to step 2; If
there was a borrow, go to step 3.
(2). Look up the rightmost remaining digits of A and B in Table 1. If A
and B are both used up, you are finished. If B is used up, use a zero as
the digit of B. Write down the digit from the table at the left end of C.
Remember whether there was a "B" at the table entry.
Scratch out the rightmost remaining digits of A and B, if any.
If there was no borrow, start step 2 again; If there was a borrow, go to
step 3. Step 3 is just like step 2, except that it uses Table 2, not Table 1.
Table 2
A\B 0 1 2 3 4 5 6 7 8 9
------------------------------------------
0 | 9B 8B 7B 6B 5B 4B 3B 2B 1B 0B
|
1 | 0 9B 8B 7B 6B 5B 4B 3B 2B 1B
|
2 | 1 0 9B 8B 7B 6B 5B 4B 3B 2B
|
3 | 2 1 0 9B 8B 7B 6B 5B 4B 3B
|
4 | 3 2 1 0 9B 8B 7B 6B 5B 4B
|
5 | 4 3 2 1 0 9B 8B 7B 6B 5B
|
6 | 5 4 3 2 1 0 9B 8B 7B 6B
|
7 | 6 5 4 3 2 1 0 9B 8B 7B
|
8 | 7 6 5 4 3 2 1 0 9B 8B
|
9 | 8 7 6 5 4 3 2 1 0 9B
A B C Borrow
Initially 9053 72 nothing
After Step 1 905 7 1 No
After Step 2 90 gone 81 Yes
After Step 3 9 gone 981 Yes
After Step 3 gone gone 8981 No
Finished.
A Case History: The Subtraction Algorithm at work.
Most of you, at some time in your lives, learned to count. In fact, you probably
learned to count starting with any given number; you had an algorithm which,
given a number, would find the number one greater. For small numbers, you could
do this in your head without strain.
When you learned to add, part of the problem was correct handling of carries.
When you add the hundreds digits of two numbers, by mentally looking the pair up
in a table of the sums of one-digit numbers, you must also remember whether there
was a carry (always a 1, if so) from the tens digits. If there was a carry, you
use your counting algorithm to get the next number larger than the one in the
addition table. In order to carry out the addition algorithm, you must first know
the counting algorithm. In the same way, to multiply, you must know and use an
addition algorithm at several stages. This pattern is frequent in the construction
of algorithms; the complex ones are based on the use of simpler ones. An algorithm
that plays an auxiliary role in another algorithm is called a subalgorithm of the
other algorithm, or a procedure.
The standard algorithm for multiplication uses, at certain steps, a subalgorithm
for addition to add up the partial products. Algorithms to add and subtract
numbers with a decimal point use an algorithm for lining up decimal points.
The design and documentation of algorithms is often simplified by referring
to already-established algorithms.
How would you add
715502413859489080310832777777777777787777777999351265714343778959999999623526 to
86279546957444495626481526614073097462138332204142610691054354354354354354354354
3652560842425?
Which of these two numbers is greater,
85889230725886718372108085241585 or 8588923075838671937210805241585?*
What is the next number after
768847474675311338864879999999999799999999999999999999999999999?
* The first one is; did you get it right?
We all learned simplified rules of arithmetic in school, which work well enough
for the numbers of up to ten digits we see in everyday life. When we get to
numbers so large that we can no longer tell at a glance which of two numbers is
larger, we must make all our rules explicit, including a system of placekeeping,
if we are to have a reasonable chance of correct results.
To test whether x>y, where x and y may be very long integers, you must read
both numbers simultaneously from right to left. To keep track of your place,
mark each digit as you read it. As you go, you will keep a tentative answer,
which you will revise whenever you see differences between x and y. We assume
neither x nor y starts with a zero.
Initially, the tentative answer is No. If you read a digit of x and a digit
of y, and they are equal, the tentative answer does not change. If they are
unequal, the tentative answer becomes Yes or No depending on whether the digit
of x is the larger or not. If you read a digit of x, and there are no more
digits of y, then the final answer is Yes; stop. If you read a digit of y,
and there are no more digits of x, the final answer if No; stop. If you find
that there are no more digits of either x or y, the tentative answer becomes the
final answer; stop.
Exercise: modify the above algorithm so that it will work even if one or both
of the numbers x and y start with one or more zeroes.
Solution: if you read a zero digit of one number, and there are no digits left
in the other, the tentative answer does not change; keep reading the number that
has not been exhausted.
To find the next number after a given number, read the number from right to left,
writing down (from right to left) a digit of the answer for every digit of the
original number you read. The process works in two stages, starting in Stage 1.
Stage 1: If you are looking at a 9, write down a zero, and stay in Stage 1.
If you are looking at a digit other than 9, write down the next
larger digit, and proceed to Stage 2. If you are looking at a blank
space, write down a 1 and stop (this is to handle numbers like 999).
Stage 2: If you are looking at a digit, copy it. If you are looking at a blank
space, stop.
_Exercise_
Write out in full the algorithm you use to perform long division.
Familiar algorithms include those for
addition, subtraction, multiplication, and division; those for solving
simultaneous equations by successive elimination of variables; that for
differentiating a formula with respect to a variable; those for estimating
the area under a curve by approximation with polygons, etc. One of
the oldest, due to Euclid, finds the greatest common divisor of two
positive numbers:
(1) Let x be the larger number, y the smaller.
(2) If y=0, x is the answer.
(3) Otherwise, let the new value of y be the remainder when x is divided
by y; let the new value of x be the old value of y. Return to Step
(2).
Example: the greatest common divisor of 195 and 75. Successive values of
x and y are:
x = 195, y = 75
x = 75, y = 45
x = 45, y = 30
x = 30, y = 15
x = 15, y = 0
The answer is 15. Notice that Euclid's algorithm uses division and size
comparison as subalgorithms.
An algorithm can be expressed in a language intelligible to man, machine,
or both. Euclid's algorithm, expressed in a language more suitable to be
carried out by a machine, looks like:
GET X
GET Y
IF X < Y THEN SWAP X WITH Y
LABEL A
IF Y=0 THEN RETURN RESULT = X
SET R = REMAINDER OF X DIVIDED BY Y
SET X = Y
SET Y = R
GO TO STEP A.
Computers are machines to carry out algorithms; to be useful, they must be
able to execute long, complicated algorithms on numerous data quickly and
reliably. A computer carries out an algorithm as expressed in one of
several precisely defined languages for that computer. An algorithm
expressed in a language executable by some actual computer is called a
program.
Programming, the design of programs, consists of two parts, often
interwoven: the design of an algorithm to solve a problem, and the
expression of that algorithm as a program within the limited notations of
a particular computer language. To learn to program, you must learn and
use some particular programming language, just as music is learned on some
particular instrument. The core of learning to program, though, is
learning to design algorithms.
There is a traditional algorithm used by Russian peasants to multiply numbers
of several digits, based on subalgorithms for
doubling, halving, and addition. To see why it
works, let's first look at a particular multiplication problem.
How much is 38 x 45? Since 38 = 19 x 2, 38 x 45 = 19 x 2 x 45 = 19 x 90.
That's 90 more than 18 x 90, so
19 x 90 = 18 x 90 + 90 = 9 x 2 x 90 + 90 = 9 x 180 + 90
Since 9 x 180 is 180 more than 8 x 180,
9 x 180 + 90 = 8 x 180 + 180 + 90 = 8 x 180 + 270
= 4 x 2 x 180 + 270 = 4 x 360 + 270
4 x 360 + 270 = 2 x 2 x 360 + 270 = 2 x 720 + 270 = 1440 + 270 = 1710.
Now that the method is clear, the process can be shortened to filling out a table.
In each row, we have two numbers we want to multiply, and another number to be
added on to the result. For the calculation above, here is the table:
A B C
38 45 0
19 90 0
18 90 90
9 180 90
8 180 270
4 360 270
2 720 270
1 1440 270
0 1440 1710
Here is an explicit algorithm for making the table.
(1) The first row across contains, in columns A and B, the numbers we want to
multiply, 38 and 45 in this example, and in column C a zero.
(2) If A=0 in the bottom row of the table, we are finished; the entry in column C
is the answer. Otherwise we need to make another row.
(3) If A is even in the bottom row, we make the next row by halving the number
in column A, doubling the number in column B, and copying the previous number
from column C.
(4) If A is odd in the bottom row, we make the next row by subtracting one from
the number is column A, copying the member in column B, and adding the number
from column B to the number in column C.
Every row in the table stands for a formula; the fifth row, above, stands for
8 x 180 + 270. People who work with algorithms find ways to represent entities
that are not just numbers by sequences of numbers; this allows using computers
that only handle numbers to solve problems that involve not only numbers, but
pictures, words, formulas, logic, and myriad others.
The successive rows represent different formulas, but each formula stands for
the same number as the one before it, so they all stand for the same number.
We get from the problem to the solution by picking a first line that is easy
to construct from the problem, and getting to a last line from which it is easy
to construct the solution. In between, we need steps that are easy to carry
out, that progress toward an acceptable last line, and that change the question
without changing the answer. That is, we go from ``What is 8 x 180 + 270?'' to
``What is 4 x 360 + 270?'' without changing the answer, 1710.
A good algorithm is like good government; it involves both stability and progress.
Progress in solving a problem comes from changing it into a simpler problem;
stability comes from assuring that each new problem has the same answer as the one
it grew from. In the Russian peasant multiplication algorithm, progress is
quaranteed because columnn A gets closer to zero at every step; it can't go on
forever, since there are only a limited number of possible values A can have,
once we know the first value. Stability is guaranteed because in each row, the
formula AxB+C has the same value.
Exercise: give algorithm for halving. Observe that to execute such an
algorithm, you must remember your place in the master algorithm while you
carry out the subordinate one.)
An algorithm, mentioned earlier, known to Euclid around 430 [?] B.C.,
finds the largest number
that evenly divides two given numbers. If we want to reduce a fraction like
385/315 to its simplest form, we find 35 as the greatest common divisor (g.c.d.)
of 385 and 315, and say 385/315 = (385/35)/(315/35) = 11/9. We can get greatest
common divisors by trial and error, but Euclid's algorithm
is a much more efficient way.
Here is a table given by a simplified form of Euclid's algorithm
finding the g.c.d. of 385 and 3l5:
A B
315 385
315 70
70 315
70 245
70 175
70 35
35 70
35 35
The algorithm sets up the first row with the smaller number in column A, and
the larger in column B. As long as B is bigger than A, it makes the next row
by copying A, and reducing B by A (subtraction). If B gets smaller than A, it
makes the next row by exchanging A with B. If B is equal to A in a row, that
number is the greatest common divisor.
The principle of stability is that the common divisors of A and B are the same
in each row. In this example, in every row both A and B are multiples of
1,5,7, and 35. If we decrease B by A, the result is still a multiple of
1,5,7, and 35, but no new common divisors are introduced (a little easy algebra
will convince you).
The principle of progress can be formulated in several ways. One way is that
the value of 2A+B decreases at every step, while staying positive.
A more efficient formulation of Euclid's algorithm uses remainders (of division)
rather than subtraction. Here it finds the g.c.d. of 315 and 385 again:
A B
315 385
70 315
35 70
0 35
As before, in the first line A is the smaller datum, B the larger. When we get
to a line with A=0, we stop, and B is the answer. Otherwise, we find the
remainder when B is divided by A. In the next line, A is that remainder, while
B is copied from A in this line.
In the improved version of the algorithm, the principle of stability is the same;
all the rows have the same common divisors and therefore the same g.c.d. The
principle of progress is that A decreases at every step, without becoming negative.
An algorithm need not work with numbers. Here is an algorithm to find a word in
the dictionary.
Insert your left index finger between pages at the beginning of the dictionary,
and your right index finger at the end. Open the dictionary somewhere between
your fingers (If you can't, you've already found the right page). Look at the
word in the top left corner of the newly opened page. If it is alphabetically
earlier than the word you are looking for, move your left index finger into the
new opening; otherwise, move your right index finger there. Here is a record of
looking up ``scutage'' in the Shorter Oxford English Dictionary.
Left finger Right finger New opening
page number word page number word page number word
1 A 2475 Zygin 1278 Monthly
1278 Monthly 2475 Zygin 1822 Sea-horse
1278 Monthly 1822 Sea-horse 1542 Pomatum
1542 Pomatum 1822 Sea-horse 1682 Redowa
1682 Redowa l822 Sea-horse 1730 Revolutionary
1730 Revolutionary 1822 Sea-horse 1780 Sailyard
1780 Sailyard 1822 Sea-horse 1800 Scantity
1800 Scantity 1822 Sea-horse 1810 Scorer
1810 Scorer 1822 Sea-horse 1816 Scriptural
1816 Scriptural 1822 Sea-horse 1820 Sea
1816 Sciptural 1822 Sea-horse 1818 Sculptile
1818 Sculptile 1820 Sea (none)
The principle of stability is that the word I'm looking for stays between my
fingers. The principle of progress is that the number of pages between my
fingers gets smaller.
Many algorithms embodied in computer programs are not reliable; when used on
certain data they give wrong answers, or they continue calculating until
someone intervenes. The way to make an algorithm reliable is to design it
around a principle of stability and a principle of progress. If you can't
formulate a principle of stability for an algorithm, it is likely to change
the problem it is solving as it goes along, and end up computing the right
answer to the wrong problem. If you can't formulate a principle of progress,
the algorithm is likely to run forever on some data. As the Russian peasant
multiplication and greatest common divisor algorithms show, it becomes much
easier to understand a new algorithm when its principle of stability (technically
known as an invariant) is presented with it.
Pascal
Algorithms meant to be performed by humans can be expressed in any way that
the humans can understand. Algorithms meant to be performed by computers
must be expressed in a language computers can interpret. Most computers
are designed to interpret algorithms written in a very crude notation
("machine language") that most humans find unsatisfactory as a language in
which to express algorithms. We meet the needs of both the human algorithm
designer and the computer interpreting the algorithm by providing a
translation; programmers write algorithms in a language designed for
convenience and expressiveness, the algorithm is translated (by another,
pre-existing computer program) into machine language, and the machine
language version of the algorithm is carried out by the computer. The
programmer need not know anything about the machine language; little
programming is done in machine language.
Pascal is a language for writing algorithms, using a mixture of English and
mathematical notation. Programs written in Pascal can be translated, by
other programs called ←compilers← or ←translators←, into the machine
languages of most popular computers. Because Pascal is a standard,
programs written in Pascal can be shared among the users of diverse
computers, and can continue to be used without change when obsolete
computers are replaced by newer ones.
Most Pascal translators accept programs in Pascal extended by notations to
make more efficient use of facilites peculiar to a particular computer.
Some translators actually accept programs written in dialects of Pascal.
The International Standards Organization (ISO) has formulated a definition
of Pascal, called Standard Pascal, which is widely accepted; normally,
programs in Standard Pascal can be expected to work with all translators of
recent design. This text uses Standard Pascal almost almost exclusively;
departures to use computer capabilities not expressible in Pascal are
explicitly labeled non-standard.
About CS106
-------------
In CS106, we use an almost standard version of the Pascal programming
language. Pascal is popular with users of small to medium-sized computers
(``micros'' and ``minis''), and has become a common language for
communication of algorithms in print. Pascal is not as well suited for
the expression of business problems as the languages PL-I and COBOL; nor
as well suited for engineering calculations as FORTRAN; nor as well suited
for processing symbolic information as SNOBOL and LISP; nor ... well, you
get the idea. No matter. Most of what you will want to program can be
said very similarly in most programming languages, and after you learn one
such language, you can learn any other in a day or so.
So, you will learn Pascal, and, with labor and attention, how to design an
algorithm systematically and correctly. You won't learn all of Pascal from
the course. This is no oversight; parts of Pascal are largely of use to
more experienced programmers, and parts are of marginal usefulness. If
you have trouble with the problems, it won't be because you don't know
Pascal well enough.
My goals are to teach you to design systematically and correctly computer
programs more complicated than anything else you have ever designed in
your life, programs so sensitive to error that a single mis-typed symbol
will probably make the program incorrect. Ideally, you will learn to
program in such a way that your first drafts of programs will contain few
errors other than slips of the pen, and that your programs can be
systematically tested and corrected (``debugged'').
Programming without standards of quality is easy. Programming is a
difficult discipline if one believes a program must be utterly trustworthy
on all valid data; that it must detect and report all invalid data; that
its results must be intelligible and unambiguous; that other programmers
must be able to adapt the program to other languages, computers, and
problems than those for which it was originally designed, long after the
original programmer has vanished.
The course notes are interlaced with Rules of Good Programming Practice.
These are only a small subset of the 927 (or was it 928?) eternal truths,
but they are very useful, and we expect you either to adhere to them or
(since they have exceptions) explain why.
We also expect you to take responsibility for yourself. The computer
center can be a difficult environment. The computer may fail for a day at
a time. Lines to use the computer may be hours long at the end of the
quarter. Assignments may be more difficult than intended. We expect you
to begin projects as early as possible; if the computer fails six hours
before a program is due, that is your problem. We expect you to use the
often overloaded computer system in a way considerate to your fellow
students; in particular, when you no longer are sure what you are doing,
get off the computer and let someone else use it. Also, delete any files
you no longer need to release storage capacity for other users. We expect
your programs to work for all valid data, and not just for the test cases
you run; to deliberately design a program that only works for the data on
which it is tested will be considered cheating. We expect you to plan to
spend twelve hours a week on this course (the university guideline for a
4-unit course) including class and computer time; you will find the course
insuitable as part of an 18-unit program.
We expect you, as the assignments become more difficult, to include
adequate explanations of how your program works. Let the hard-pressed
grader, who perhaps just took the course the previous quarter, know in
outline what your methods are. And if your native language is English, we
would appreciate a demonstration of the fact. We expect you to respect the
privacy of other people's computer files; the fact that someone has not
fully protected his files does not give you the right to read them.
Okay, we've told you the worst. On the good side, the teaching assistants,
consultants, and professor are there to help out. Not by doing your work
for you, but by serving as models of how to think about programming. Most
of the time, the computer center is a friendly environment. And the
computer itself is the most versatile tool you will ever use. You have
signed up to vastly extend your powers to use and create information. I
think you will be glad you did.
Programs
A ←program← in Pascal is a complete algorithm, describing a computation in
sufficient detail that it can be carried out by a computer. A Pascal
program contains information about the resources the computer will need to
perform the computation, and detailed instructions about the sequence of
computational steps. The simplest type of Pascal program has the form
PROGRAM name (OUTPUT);
BEGIN
command;
command;
...
...
command
END.
where the programmer fills in the name of his program where `name' appears
in the form, and fills in commands to carry out the desired computation
where `command' appears in the form.
Program names can be made up at will from the English alphabet. There are
many kinds of commands, but every program will contain some commands to
print its results so that we can see them. The form of such a command can be
WRITE (expression, expression, ..., expression)
where the expressions can be numbers, or formulas built up from numbers
using symbols that express the operations of arithmetic and elementary
functions.
*****************
1. (Material from my older Pascal Notes goes here)
We need a compact, unambiguous way to express the forms of programs,
commands, etc., that are acceptable in Pascal. We will use ←transition
diagrams← for these forms. The transition diagram for programs is:
program: PROGRAM name (OUTPUT);
BEGIN command ;
END.
Any path through the diagram is a legitimate form for a program. Lower
case names, in rectangular boxes, like "command" stand for sections which
the programmer must fill in. In the diagram above, every time we come to
"command", we have to fill in a legitimate command according to another
transition diagram:
command: WRITE ( expression ,
WRITELN )
Standard Algorithms in Pascal
Electronic computers have built-in algorithms for elementary arithmetic.
Usually the built-in algorithms include addition, subtraction,
multiplication, division with and without remainder, and testing whether one
number is greater than, equal to, or less than, another. Pascal uses these
algorithms. A Pascal programmer need not concern himself with how division
is done; he writes 22/7 in his program, and the result 3.142857 is
automatically supplied. Other functions, including the log, trig, and
exponential functions, are not built into the computer, but can be computed
by small programs for subalgorithms, which the Pascal translator
automatically includes in any
program that needs them. If a Pascal programmer writes the expression
LOG(2) + TAN(3.1415926/4), the translator provides for finding the
logarithm, adding, etc., by a fast and accurate algorithm. The forms of
expression in Pascal that use the standard numerical algorithms are these,
where A and B are numbers, or expressions with numerical values:
******************fill in
A + B, A - B, A/B, SIN(A), COS(A), ... have their customary meaning.
A * B is the product of A and B. Remember not to use A x B; Pascal won't
understand.
SQRT(A) is the positive square root of A (A>=0)
SQR(A) is A↑2 (Don't confuse SQRT with SQR)
LN(A) is the natural (base = 2.71828...) logarithm.
LOG(A) is the common (base 10) logarithm.
...
...
*******************fill in
When several standard algorithms are used in the same expression, as in
2 + 3/4 * 5 - 6, a set of conventions determine what is done first.
Generally, where possible, multiplications and divisions are done first,
from left to right, giving in the example 3/4 = 0.75 and 0.75 * 5 = 3.75;
next additions and subtractions are done from left to right, giving
2 + 3.75 = 5.75 and 5.75 - 6 = -0.25, the value of the expression.
Parentheses may be used where the convention would not be the same as the
programmer's intention; 2 + 3/(4 * 5) - 6 gives
4 * 5 = 20, 3/20 = 0.15, 2 + 0.15 = 2.15, 2.15 - 6 = -3.85.